# -*- coding: utf-8 -*-
# 问题描述
# 将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数：
# P   A   H   N
# A P L S I I G
# Y   I   R
# 之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"

# 实现一个将字符串进行指定行数变换的函数:
# string convert(string s, int numRows);

# 示例 1:
# 输入: s = "PAYPALISHIRING", numRows = 3
# 输出: "PAHNAPLSIIGYIR"

# 示例 2:
# 输入: s = "PAYPALISHIRING", numRows = 4
# 输出: "PINALSIGYAHRPI"
# 解释:
# P     I     N
# A   L S   I G
# Y A   H R
# P     I

# # 解题思路建立一个足够大的矩阵
# # 遍历s，找到每一个元素在矩阵中的行和列
# # 然后删除矩阵中的填充元素则能得到答案
# class Solution(object):
#     def convert(self, s, numRows):
#         """
#         :type s: str
#         :type numRows: int
#         :rtype: str
#         """
#         if numRows==1:
#             return s;

#         max_col = len(s) / (2 * numRows - 2) * (numRows - 1) + len(s) % (2 * numRows - 2);
#         rtn = ["#"] * (max_col * numRows);
#         col = -1;

#         for index in xrange(len(s)):
#             row = index % (2 * numRows - 2);
#             if row >= numRows:
#                 row = 2 * numRows - 2 - row;
#                 col += 1;
#             if row==0:
#                 col += 1;
#             rtn[row * max_col + col] = s[index];

#         return ("".join(rtn)).replace("#", "");








# 阅读官方提供的答案
# 思路大致和上方的思路相似，但是更简单了
# 实际上我们是不需要计算列的，我们只需要计算每个元素在哪一行，然后依次把每一行都加在一起，就是最终答案了
class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows==1:
            return s;

        lines = [""] * numRows;

        for index in xrange(len(s)):
            row = index % (2 * numRows - 2);
            if row >= numRows:
                row = 2 * numRows - 2 - row;
            lines[row] += s[index];

        rtn = "";
        for index in xrange(numRows):
            rtn += lines[index];
        return rtn;

t = Solution();
print t.convert("PAYPALISHIRING", 4);